﻿/*------------------------------------------------------------------------

CXXLAVLTREE.HPP v3.2

Copyright 楊志賢 CxxlMan, 2008 - 2014
All Rights Reserved


------------------------------------------------------------------------*/

#if !defined(__CXXLAVLTREE_HPP_CxxlMan)
#define __CXXLAVLTREE_HPP_CxxlMan

#include "CXXLLIST.HPP"

namespace CxxlMan
{

/*
  T = 要包裝的物件型別，須是 cxxlObject 的延伸類別
  K = Key 值，作為識別用
  isUnique = Key 值若不可重複設為 true，否則為 false 
*/
template <typename T, typename K, bool isUnique>
class cxxlAVL_Tree:virtual public cxxlObject
{
protected:

  CriticalSec csObject;

private:

  class Node
  {
    int AVL_chk;     // 判斷左右子樹的高度差距
                     // 左右相等為 0，左大於右為負，右大於左為正
                     // 依 AVL-tree 的定義，其值應 -1 至 1
    Smart_Ptr<T> Obj_Ptr;
    K key;

    Node *parent,*left,*right;

  public:
    // Constructor
    Node(T *S,K Key,cxxlAVL_Tree<T,K,isUnique> *Host,
         Node *Parent
        )
      :Obj_Ptr(S,Host),key(Key)
    {
      AVL_chk = 0;
      parent = Parent;
      left = right = NULL;
    }

    ~Node()  // Destructor
    {
    }

    K cxxlFASTCALL GetKey()
    {
      return key;
    }

    T * cxxlFASTCALL GetObj() const
    {
      return (T *)Obj_Ptr;
    }

    Node * cxxlFASTCALL GetParentNode() const
    {
      return parent;
    }

    Node * cxxlFASTCALL GetRightNode() const
    {
      return right;
    }

    Node * cxxlFASTCALL GetLeftNode() const
    {
      return left;
    }
    
    bool cxxlFASTCALL isParentEmpty(void) const // 父節點是否為空
    {
      return parent == NULL;
    }

    bool cxxlFASTCALL isRightEmpty() const
    {
      return right == NULL; 
    }
    
    bool cxxlFASTCALL isLeftEmpty() const
    {
      return left == NULL; 
    }

    // 調整 AVL_chk 值，並回覆調整後的值
    int cxxlFASTCALL operator >> (int v)
    {
      return  AVL_chk += v;
    }
    int cxxlFASTCALL operator << (int v)
    {
      return  AVL_chk -= v;
    }

    void cxxlFASTCALL SetParentNode(Node *toNode)  // 設定父節點
    {
      parent = toNode;
    }
    
    void cxxlFASTCALL SetLeftNode(Node *toNode)  // 設定 LeftNode
    {
      left = toNode;
    }
    
    void cxxlFASTCALL SetRightNode(Node *toNode) // 設定 RightNode    
    {
      right = toNode;
    }

    int cxxlFASTCALL Get_AVL_chk()
    {
      return AVL_chk;
    }
    
    void cxxlFASTCALL Set_AVL_chk(int v)
    {
      AVL_chk = v;
    }

    // 左節點非空的情況下，找出前一個 Node
    Node * cxxlFASTCALL FindPrevNode() const
    {
      Node *PrevNode = GetLeftNode();
      while(!PrevNode->isRightEmpty())
        PrevNode = PrevNode->GetRightNode();

      return PrevNode;      
    }

    // 右節點非空的情況下，找出下一個 Node
    Node * cxxlFASTCALL FindNextNode() const
    {
      Node *NextNode = GetRightNode();
      while(!NextNode->isLeftEmpty())
        NextNode = NextNode->GetLeftNode();

      return NextNode;      
    }

  };

  Node *root;

  unsigned long count;


  void cxxlFASTCALL AddToRoot(T *addObj,K addKey)
  {
    root = new Node (addObj,addKey,this,NULL);
    ++count;
  }

  // 排序檢測，延伸類別須實作此函數
  // 要讓 O_Key 鍵值所代表的物件排在 左 回答 true，否則 false
  virtual bool cxxlFASTCALL isLeftAt(K O_Key,K addKey) const = 0;

  // 這函數用來決定在容器中 O_Key 鍵值所代表的物件，是不是 findKey 所要尋找的  
  // 是 回答 true，否則 false，延伸類別須實作此函數
  virtual bool cxxlFASTCALL isEqual(K O_Key,K findKey)  const = 0;

  // cxxlList_Create(K filterKey) 要用的的過濾條件，延伸類別須覆寫此函數
  // 條件符合 回答 true，否則 false
  virtual bool cxxlFASTCALL cxxlList_CreateFilter(K O_Key,K filterKey) const
  {
    return false;
  }

  // Clone() 時用來產生延伸類別的物件
  // 所以延伸別必須覆載
  virtual cxxlAVL_Tree<T,K,isUnique> * cxxlFASTCALL CreateSelf(ISpirit *spirit) const
  {
    return NULL;
  }


  void cxxlFASTCALL AddToRight(T *toAdd,K Key,Node *Parent)
  {
    Parent->SetRightNode(new Node(toAdd,Key,this,Parent));
    AdjustAVLForAdd(Parent,false);
    ++count;
  }

  void cxxlFASTCALL AddToLeft(T *toAdd,K Key,Node *Parent)
  {
    Parent->SetLeftNode(new Node(toAdd,Key,this,Parent));
    AdjustAVLForAdd(Parent,true);
    ++count;
  }

  // 由指定的節點開始往上修改各節點的 AVL_chk 值
  // atLeft 為 true 表示是從指定節點左邊增加
  void cxxlFASTCALL AdjustAVLForAdd(Node *N,bool atLeft);

  // 由指定的節點開始往上修改各節點的 AVL_chk 值
  // atLeft 為 true 表示是從指定節點左邊減少
  void cxxlFASTCALL AdjustAVLForDel(Node *N,bool atLeft);

  // 傳入要調整的帶頭節點(父節點)，傳回調整後替代的帶頭節點
  // 對 AVL_chk 為 -2 的帶頭節點做調整
  Node * cxxlFASTCALL HigherAtLeft(Node *N);

  // 傳入要調整的帶頭節點(父節點)，傳回調整後替代的帶頭節點
  // 對 AVL_chk 為 2 的帶頭節點做調整
  Node * cxxlFASTCALL HigherAtRight(Node *N);

  // 刪除指定的 Node
  void cxxlFASTCALL ReleaseNode(Node *N);


  // 刪除指定節點以下所有節點(採用後序搜尋)
  void cxxlFASTCALL ClearAll(Node *N)
  {
    if(N != NULL)
    {
      ClearAll(N->GetLeftNode());
      ClearAll(N->GetRightNode());
      delete N;
    }  
  }

  // 找到指定的 findKey 回覆所在的 Node，否則回覆 NULL
  Node * cxxlFASTCALL FindNode(K findKey) const
  {
    Node *N = root;
    while(true)
    {
      K O_Key = N->GetKey();
      if(isEqual(O_Key,findKey))  // 找到
        return N;
      else if(isLeftAt(O_Key,findKey))  // 到右節點去找
      {
        if(N->isRightEmpty()) return NULL;
        N = N->GetRightNode();
      }    
      else                             // 到左節點去找
      {
        if(N->isLeftEmpty()) return NULL;
        N = N->GetLeftNode();
      }
    }
  }


  // 以中序搜尋的方式將所有物件放入 cxxlList_Temp
  void cxxlFASTCALL Init_cxxlList(Node *N, cxxlList<T> *cxxlList_Temp) const
  {
    if(N != NULL)
    {
      Init_cxxlList(N->GetLeftNode(), cxxlList_Temp);
    
      cxxlList_Temp->Push_Back(N->GetObj());
    
      Init_cxxlList(N->GetRightNode(), cxxlList_Temp);
    }
  }

  // 以中序搜尋的方式將符合過濾條件的物件放入 cxxlList_Temp
  void cxxlFASTCALL Init_cxxlList(Node *N, cxxlList<T> *cxxlList_Temp, K filterKey) const
  {
    if(N != NULL)
    {
      Init_cxxlList(N->GetLeftNode(), cxxlList_Temp, filterKey);
    
      if(cxxlList_CreateFilter(N->GetKey(),filterKey))
      {
        cxxlList_Temp->Push_Back(N->GetObj());
      }
    
      Init_cxxlList(N->GetRightNode(), cxxlList_Temp, filterKey);
    }
  }


  void cxxlFASTCALL CloneNode(cxxlAVL_Tree<T,K,isUnique> *R, Node *node) const
  {
    if(node != NULL)
    {
      R->Add(node->GetObj(),node->GetKey());

      CloneNode(R,node->GetLeftNode());
      CloneNode(R,node->GetRightNode());      
    }
}


public:
  // 若鍵值不可重複 isUnique 設為 true
  cxxlAVL_Tree(ISpirit *spirit = Spirit_Easy)  // Constructor
    :cxxlObject(spirit)
  {
    root = NULL;
    count = 0;    
  }

  virtual ~cxxlAVL_Tree()  // Destructor
  {
    ClearAll();
  }

  // 取得物件的個數
  unsigned long cxxlFASTCALL GetCount() const
  {
    return count;
  }

  // 放棄持有所有物件
  void cxxlFASTCALL ClearAll()
  {
    csObject.Enter();
    ClearAll(root);  
    root = NULL;
    count = 0;  
    csObject.Leave();
  }

  // 放入一個物件，回傳值只對 Unique Tree 才有用，
  // 若這是 Unique Tree 且 addKey 已有存在則會回復 false 
  bool cxxlFASTCALL Add(const Smart_Ptr<T> &addObj,K addKey);

  // 刪除(放棄持有)指定的物件
  // 找不到 或 空的 傳回 false
  bool cxxlFASTCALL Delete(K delKey)
  {
    CriticalSecHandle AutoCSH(csObject);
    if(root != NULL)
    {
      Node *N = FindNode(delKey);
      if(N != NULL)
      {
        ReleaseNode(N);
        return true; 
      }
    } 
  
    return false;
  }

  // 取回並移除指定的物件 
  // 找不到 或 空的 傳回的智慧指標包裹的是 NULL，可用 Smart_Ptr::isNULL() 檢查 
  Smart_Ptr<T> cxxlFASTCALL Pump(K findKey)
  {
    CriticalSecHandle AutoCSH(csObject);
    if(root != NULL)
    {
      Node *N = FindNode(findKey);
      if(N != NULL)
      {
        Smart_Ptr<T> temp(N->GetObj());
        ReleaseNode(N);
        return temp;
      }
    } 
  
    return Smart_Ptr<T>(NULL);
  }

  // 取得含指定的物件的智慧指標 
  // 找不到 或 空的 傳回的智慧指標包裹的是 NULL，可用 Smart_Ptr::isNULL() 檢查 
  Smart_Ptr<T> cxxlFASTCALL GetObj(K findKey) const
  {
    CriticalSecHandle AutoCSH(csObject);
    if(root != NULL)
    {
      Node *N = FindNode(findKey);
      if(N != NULL)
        return N->GetObj();
    } 
  
    return Smart_Ptr<T>(NULL);
  }

  // 將所有物件放入一個串列物件後傳回
  Smart_Ptr<cxxlList<T> > cxxlFASTCALL cxxlList_Create() const
  {
    CriticalSecHandle AutoCSH(csObject);
    cxxlList<T> *cxxlList_Temp = new cxxlList<T>(this->GetSpirit());
  
    Init_cxxlList(root, cxxlList_Temp);
  
    return Smart_Ptr<cxxlList<T> >(cxxlList_Temp);
  }

  // 將符合過濾條件的物件放入一個串列物件後傳回
  Smart_Ptr<cxxlList<T> > cxxlFASTCALL cxxlList_Create(K filterKey) const
  {
	CriticalSecHandle AutoCSH(csObject);
    cxxlList<T> *cxxlList_Temp = new cxxlList<T>(this->GetSpirit());
  
    Init_cxxlList(root, cxxlList_Temp,  filterKey);
  
    return Smart_Ptr<cxxlList<T> >(cxxlList_Temp);
  }

  // 自我複製
  // 傳回相同內容的同類形容器物件
  // 兩個獨立的容器共同擁有相同的物件
  // 但各自的增刪互不影響  
  Smart_Ptr<cxxlAVL_Tree<T,K,isUnique> > cxxlFASTCALL Clone() const
  {
    CriticalSecHandle AutoCSH(csObject);

	cxxlAVL_Tree<T,K,isUnique> *R = CreateSelf(this->GetSpirit());
    CloneNode(R,root);
    return Smart_Ptr<cxxlAVL_Tree<T,K,isUnique> >(R);
  }

};

// 由指定的節點開始往上修改各節點的 AVL_chk 值
// atLeft 為 true 表示是從指定節點左邊增加
template <typename T, typename K, bool isUnique>
void cxxlFASTCALL cxxlAVL_Tree<T,K,isUnique>::AdjustAVLForAdd(Node *N,bool atLeft)
{
  Node *NowNode = N;
  Node *ParentNode;
  bool f = true;
  int v;

  if(atLeft)
    v = *NowNode << 1;
  else
    v = *NowNode >> 1;

  while(f)
  {
    switch(v)
    {
    case -1: case 1:
      ParentNode = NowNode->GetParentNode();
      if(ParentNode == NULL)
        f = false;
      else
      {
     	  if(ParentNode->GetLeftNode() == NowNode)
     	    v = *ParentNode << 1;
     	  else
     	    v = *ParentNode >> 1;
     	  NowNode = ParentNode;
      }
      break;
    case -2:
      HigherAtLeft(NowNode);
      f = false;
      break;
    case 2:
      HigherAtRight(NowNode);
    case 0:
      f = false;
    }
  }    
}


// 由指定的節點開始往上修改各節點的 AVL_chk 值
// atLeft 為 true 表示是從指定節點左邊減少
template <typename T, typename K, bool isUnique>
void cxxlFASTCALL cxxlAVL_Tree<T,K,isUnique>::AdjustAVLForDel(Node *N,bool atLeft)
{
  Node *NowNode = N;
  Node *ParentNode;
  bool f = true;
  int v;
  
  if(atLeft)
    v = *NowNode >> 1;
  else
    v = *NowNode << 1;

  while(f)
  {
    switch(v)
    {
    case 0:
      ParentNode = NowNode->GetParentNode();
      if(ParentNode == NULL)
        f = false;
      else
      {
     	  if(ParentNode->GetLeftNode() == NowNode)
     	    v = *ParentNode >> 1;
     	  else
     	    v = *ParentNode << 1;
     	  NowNode = ParentNode;
      }
      break;
    case -2:
      NowNode = HigherAtLeft(NowNode);
      v = NowNode->Get_AVL_chk();
      break;
    case 2:
      NowNode = HigherAtRight(NowNode);
      v = NowNode->Get_AVL_chk();
      break;
    case 1: case -1:
      f = false;
    }
  }
}

// 傳入要調整的帶頭節點(父節點)，傳回調整後替代的帶頭節點
// 對 AVL_chk 為 -2 的帶頭節點做調整
template <typename T, typename K, bool isUnique>
typename cxxlAVL_Tree<T,K,isUnique>::Node *
cxxlFASTCALL cxxlAVL_Tree<T,K,isUnique>::HigherAtLeft(typename cxxlAVL_Tree<T,K,isUnique>::Node *N)
{
  cxxlAVL_Tree<T,K,isUnique>::Node *NewHead;

  int v = N->GetLeftNode()->Get_AVL_chk();
  if(v == 1)
  {
    NewHead = N->GetLeftNode()->GetRightNode();
    
    switch(NewHead->Get_AVL_chk())
    {
    case -1:
      *NewHead >> 1;
      *N >> 3;
      *(N->GetLeftNode()) << 1;
      break;
    case 0:
      *N >> 2;
      *(N->GetLeftNode()) << 1;
      break;
    case 1:
      *NewHead << 1;
      *N >> 2;
      *(N->GetLeftNode()) << 2;
    }
    NewHead->SetParentNode(N->GetParentNode());
    
    N->GetLeftNode()->SetRightNode(NewHead->GetLeftNode());
    if(!NewHead->isLeftEmpty())
      NewHead->GetLeftNode()->SetParentNode(N->GetLeftNode());
    NewHead->SetLeftNode(N->GetLeftNode());
    N->GetLeftNode()->SetParentNode(NewHead);
    
    N->SetLeftNode(NewHead->GetRightNode());
    if(!NewHead->isRightEmpty())
      NewHead->GetRightNode()->SetParentNode(N);    
    NewHead->SetRightNode(N);
    N->SetParentNode(NewHead);
  }
  else // v <= 0
  {
    NewHead = N->GetLeftNode();
    *NewHead >> 1;
    *N >> ((v == -1)?2:1);
    
    NewHead->SetParentNode(N->GetParentNode());
    N->SetParentNode(NewHead);
    N->SetLeftNode(NewHead->GetRightNode());
    if(!NewHead->isRightEmpty())
      NewHead->GetRightNode()->SetParentNode(N);
    NewHead->SetRightNode(N);
  }
  
  Node *NN = NewHead->GetParentNode();

  if(NN == NULL)
    root = NewHead;
  else if(NN->GetLeftNode() == N)
    NN->SetLeftNode(NewHead);
  else
    NN->SetRightNode(NewHead);

  return NewHead;  
}

// 傳入要調整的帶頭節點(父節點)，傳回調整後替代的帶頭節點
// 對 AVL_chk 為 2 的帶頭節點做調整
template <class T, class K, bool isUnique>
typename cxxlAVL_Tree<T,K,isUnique>::Node * 
cxxlFASTCALL cxxlAVL_Tree<T,K,isUnique>::HigherAtRight(typename cxxlAVL_Tree<T,K,isUnique>::Node *N)
{
  Node *NewHead;

  int v = N->GetRightNode()->Get_AVL_chk();

  if(v == -1)
  {
    NewHead = N->GetRightNode()->GetLeftNode();
  
    switch(NewHead->Get_AVL_chk())
    {
    case 1:
      *NewHead << 1;
      *N << 3;
      *(N->GetRightNode()) >> 1;
      break;
    case 0:
      *N << 2;
      *(N->GetRightNode()) >> 1;
      break;
    case -1:
      *NewHead >> 1;
      *N << 2;
      *(N->GetRightNode()) >> 2;    
    }    
  
    NewHead->SetParentNode(N->GetParentNode());
  
    N->GetRightNode()->SetLeftNode(NewHead->GetRightNode());
    if(!NewHead->isRightEmpty())
      NewHead->GetRightNode()->SetParentNode(N->GetRightNode());
    NewHead->SetRightNode(N->GetRightNode());
    N->GetRightNode()->SetParentNode(NewHead);
  
    N->SetRightNode(NewHead->GetLeftNode());
    if(!NewHead->isLeftEmpty())
      NewHead->GetLeftNode()->SetParentNode(N);
    NewHead->SetLeftNode(N);
    N->SetParentNode(NewHead);    
  }
  else  // v >= 0
  {
    NewHead = N->GetRightNode();
    *NewHead << 1;
    *N << ((v == 1)?2:1);

    NewHead->SetParentNode(N->GetParentNode());
    N->SetParentNode(NewHead);
    N->SetRightNode(NewHead->GetLeftNode());
    if(!NewHead->isLeftEmpty())
      NewHead->GetLeftNode()->SetParentNode(N);
    NewHead->SetLeftNode(N);
  } 

  Node *NN;
  NN = NewHead->GetParentNode();

  if(NN == NULL)
    root = NewHead;
  else if(NN->GetLeftNode() == N)
    NN->SetLeftNode(NewHead);
  else
    NN->SetRightNode(NewHead);

  return NewHead;  
}

// 刪除指定的 Node
template <class T, class K, bool isUnique>
void cxxlFASTCALL cxxlAVL_Tree<T,K,isUnique>::ReleaseNode(Node *N)
{
  Node *SubstituteNode; // 要替代的節點
  int fDir;    // 向左找替代節點為 -1
               // 向右找替代節點為 1
               // 兩方都空節點為 0

  Node *Adjust = NULL; // 開始要調整的節點
  bool AdjustDir; // 指示 Adjust 左右哪個節點減少，true 為左，false 為右

  if(!N->isLeftEmpty())
  {
    fDir = -1;
    SubstituteNode = N->FindPrevNode();
  }
  else if(!N->isRightEmpty())
  {
    fDir = 1;
    SubstituteNode = N->FindNextNode();
  }
  else
  {
    fDir = 0;
    SubstituteNode = NULL;
    if(!N->isParentEmpty())
    {
      Adjust = N->GetParentNode();
      if(N->GetParentNode()->GetLeftNode() == N)
        AdjustDir = true;
      else
        AdjustDir = false;
    }
  }

  // 處理 SubstituteNode 原本連結的節點
  if(fDir == -1)
  {
    if(N->GetLeftNode() != SubstituteNode)  // 替代節點不是左節點
    {
      Adjust = SubstituteNode->GetParentNode();
      AdjustDir = false;
      Adjust->SetRightNode(SubstituteNode->GetLeftNode());
      if(!SubstituteNode->isLeftEmpty())
        SubstituteNode->GetLeftNode()->SetParentNode(SubstituteNode->GetParentNode());
    }
    else
    {
    	Adjust = SubstituteNode;
      AdjustDir = true;
    }
  }
  else if(fDir == 1)
  {
    if(N->GetRightNode() != SubstituteNode)  // 替代節點不是右節點
    {
      Adjust = SubstituteNode->GetParentNode();
      AdjustDir = true;
      Adjust->SetLeftNode(SubstituteNode->GetRightNode());
      if(!SubstituteNode->isRightEmpty())
        SubstituteNode->GetRightNode()->SetParentNode(SubstituteNode->GetParentNode());
    }
    else
    {
      Adjust = SubstituteNode;
      AdjustDir = false;
    }
  }

    // 對上方的處理及設定 AVL_chk
  if(fDir != 0)
  {
    SubstituteNode->Set_AVL_chk(N->Get_AVL_chk());
    SubstituteNode->SetParentNode(N->GetParentNode());
  }
  if(!N->isParentEmpty())
  {
    if(N->GetParentNode()->GetLeftNode() == N)
      N->GetParentNode()->SetLeftNode(SubstituteNode);
    else
      N->GetParentNode()->SetRightNode(SubstituteNode);
  }
  else // N 是 root
    root = SubstituteNode;

  // 對左方的處理
  if(fDir == -1)
  {
    if(N->GetLeftNode() != SubstituteNode)  // 替代節點不是左節點才處理
    {
      N->GetLeftNode()->SetParentNode(SubstituteNode);
      SubstituteNode->SetLeftNode(N->GetLeftNode());
    }  
  }

  // 對右方的處理
  switch(fDir)
  {
  case 1:
    if(N->GetRightNode() != SubstituteNode)  // 替代節點不是右節點才處理
    {
      N->GetRightNode()->SetParentNode(SubstituteNode);
      SubstituteNode->SetRightNode(N->GetRightNode());
    }
    break;
  case -1:
    if(!N->isRightEmpty())
    {
      N->GetRightNode()->SetParentNode(SubstituteNode);
      SubstituteNode->SetRightNode(N->GetRightNode());
    }
  }

  if(Adjust != NULL)
    AdjustAVLForDel(Adjust,AdjustDir);    
  
  --count; delete N;
}

// 放入一個物件，回傳值只對 Unique Tree 才有用，
// 若這是 Unique Tree 且 addKey 已有存在則會回復 false 
template <class T, class K, bool isUnique>
bool cxxlFASTCALL cxxlAVL_Tree<T,K,isUnique>::Add(const Smart_Ptr<T> &addObj,K addKey)
{
  CriticalSecHandle AutoCSH(csObject);
  bool R = true;
  if(root == NULL)  // 若尚未含有任何物件
    AddToRoot(addObj,addKey);
  else                     // 找出插入位置再放入
  {
    Node *Temp = root;

    while(true)
    {
      K O_Key = Temp->GetKey();
    
      if(isUnique && isEqual(O_Key,addKey))
      {
        R = false;
        break;
      }

      if(isLeftAt(O_Key,addKey)) // 往右處理
      {
        if(Temp->isRightEmpty()) 
        {
          AddToRight(addObj,addKey,Temp);
          break;
        }  
        else
          Temp = Temp->GetRightNode();
      }
      else  // 往左處理
      {
        if(Temp->isLeftEmpty()) 
        {
          AddToLeft(addObj,addKey,Temp);                      
          break;
        }  
        else
          Temp = Temp->GetLeftNode();
      }
    }
  }
  return R;
}


}   /* namespace CxxlMan */
#endif

